Modern internet routers determine data routing based on searching for a packet destination Internet Protocol address (DIP) in a database of forwarding information known as a routing table. The routing table, rather than storing a full DIP, stores only some of the leading portion, known as a prefix. The prefix comprises some number of the most significant bits (MSB) of the DIP. The remaining bits are treated as “don't care” bits for purpose of a DIP search in the routing table. Computers that belong to a subnetwork are addressed by a common prefix in their IP address.
The most specific of the matching table entries—the one with the longest subnet mask—is called the longest prefix match (LPM). This is the entry in the routing table in which the largest number of leading address bits of the destination address match those in the table entry. The router selects this entry to route the packet.
Searching the routing table for the LPM is a bottleneck in routing throughput. Implementing LPM is challenging, as the DIP of each incoming packet has to be compared against the entries of the routing table, which can be very large, for example more than 500,000 entries, in order to find the best (longest) prefix match. Various hardware-based solutions have been proposed, but the circuitry required to implement such solutions becomes complex. Moreover, the increasing amount of Internet traffic and demands for reduced latency have resulted in relatively costly router circuitry having high power consumption and heat dissipation.
Some methods for implementing a longest prefix match in a routing table involve constructing a binary search tree on prefix lengths with markers. A method of this sort is described in an article entitled, “Scalable High-Speed Prefix Matching,” by Waldvogel et al., published in Proceedings of the ACM SIGCOMM '97 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, pages 25-36 (1997), which is incorporated herein by reference. The method requires addition of new entries, called markers, in the binary search tree to ensure that the correct result is obtained for all the packets. When there is a match on a given node of the tree, that information can be used to narrow down the search.
U.S. Patent Application Publication 2017/0366459, whose disclosure is incorporated herein by reference, describes an optimization of the solution described in the above-noted Waldvogel paper that can be easily implemented in hardware. The search jumps on a match to the next level of the tree that needs to be checked, thus reducing both the number of accesses and the number of markers. The jump captures most of the benefits that can be extracted from information provided by a match.
Documents incorporated by herein reference are to be considered an integral part of the application except that, to the extent that any terms are defined in these incorporated documents in a manner that conflicts with definitions made explicitly or implicitly in the present specification, only the definitions in the present specification should be considered.